/**
 * comp2017 - assignment 2
 * <your name>
 * <your unikey>
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <stdbool.h>

#include "ymirdb.h"

// global data
snapshot* snapshots = NULL;
entry* current = NULL;
static int snapshot_id = 1;

//
// We recommend that you design your program to be
// modular where each function performs a small task
//
// e.g.
//
// command_bye
// command_help
// ...
// entry_add
// entry_delete
// ...
//

int canBeDelete(entry* target) {
	if(target->backward_size == 0) {
		return 1;
	}else {
		return 0;
	}
}

void updateSimple(entry* target) {
	int is_simple = 1;

	for(int i=0;i<target->length;i++) {
		if((target->values)[i].type == ENTRY) {
			is_simple = 0;
		}
	}

	target->is_simple = is_simple;
}

int hasForwardEntry(entry* target, entry* forward) {

	for(int i=0;i<target->forward_size;i++) {
		if((target->forward)[i] == forward) {
			return 1;
		}
	}
	return 0;
}

int hasBackWardEntry(entry* target, entry* backward) {

	for(int i=0;i<target->backward_size;i++) {
		if((target->backward)[i] == backward) {
			return 1;
		}
	}
	return 0;
}

void addForwardToEntry(entry* target, entry* forward) {
	// insert to the end 
	(target->forward)[target->forward_size] = forward;
	(target->forward_size)++;
}

void delForwardEntry(entry* target, entry* forward) {

	for(int i=0;i<target->forward_size;i++) {
		if((target->forward)[i] == forward) {
			// find the forward entry to be deleted 
			// delete it and move 
			for(int j=(i+1);j<target->forward_size;j++) {
				// swap j and j - 1
				entry* temp = (target->forward)[j];
				(target->forward)[j] = (target->forward)[j - 1];
				(target->forward)[j - 1] = temp;
			}
			(target->forward_size)--;
			updateSimple(target);
			break;
		}
	}
}

void addBackwardToEntry(entry* target, entry* backward) {
	// insert to the end 
	(target->backward)[target->backward_size] = backward;
	(target->backward_size)++;
}

void delBackwardEntry(entry* target, entry* backward) {
	for(int i=0;i<target->backward_size;i++) {
		if((target->backward)[i] == backward) {
			// find the backward entry to be deleted 
			// delete it and move 
			for(int j=(i+1);j<target->backward_size;j++) {
				// swap j and j - 1
				entry* temp = (target->backward)[j];
				(target->backward)[j] = (target->backward)[j - 1];
				(target->backward)[j - 1] = temp;
			}
			(target->backward_size)--;
			break;
		}
	}
}

entry* findEntry(entry* head, char* key) {
	entry* ptr = head->next;

	while(ptr != head) {
		if(strcmp(ptr->key, key) == 0) {
			return ptr;
		}
		ptr = ptr->next;
	}

	return NULL;

}

snapshot* findSnapshot(snapshot* head, int id) {
	snapshot* ptr = head->next;

	while(ptr != head) {
		if(ptr->id == id) {
			return ptr;
		}
		ptr = ptr->next;
	}

	return NULL;
}

void freeEntry(entry* target) {
	if(target->length != 0)
		free(target->values);
	if(target->forward_size != 0)
		free(target->forward);
	if(target->backward_size != 0)
		free(target->backward);

	free(target);
}

void deleteEntry(entry* head, char* key) {
	// find the entry to be deleted

	entry* res = findEntry(head, key);

	res->prev->next = res->next;
	res->next->prev = res->prev;

	freeEntry(res);
	
}

void deleteAll(entry* head) {
	entry* ptr = head->next;

	while(ptr != head) {
		entry* next = ptr->next;
		deleteEntry(head, ptr->key);
		ptr = next;
	}
}


void freeSnapshotEntries(snapshot* target) {
	// free snapshot's entries
	deleteAll(target->entries);
	if(target->entries->length != 0)
		free(target->entries->values);
	if(target->entries->forward_size != 0)
		free(target->entries->forward);
	if(target->entries->backward_size != 0)
		free(target->entries->backward);
	free(target->entries);
	target->entries = NULL;
}

void deleteSnapshot(snapshot* head, int id) {
	// find the snapshot to be deleted

	snapshot* res = findSnapshot(head, id);

	res->prev->next = res->next;
	res->next->prev = res->prev;

	freeSnapshotEntries(res);

	free(res);
	
}

void deleteAllSnapshots(snapshot* head) {
	snapshot* ptr = head->next;

	while(ptr != head) {
		snapshot* next = ptr->next;
		deleteSnapshot(head, ptr->id);
		ptr = next;
	}
}

char* upcase(char* str) {
	int length = strlen(str);
	for(int i=0;i<length;i++) {
		if(str[i] > 90) {
			str[i] = str[i] - 32;
		}
	}
	return str;
}

static inline char isDigit(char c) { return (c >= '0' && c <= '9');}

int getDigitsFromStr(char* str) {
	int length = strlen(str);
	int res = 0;
	int is_neg = 0;
	int start = 0;

	if(str[0] == '-') {
		start = 1;
		is_neg = 1;
	}

	for(int i=start;i<length;i++) {
		res = res * 10 + (str[i] - '0');
	}

	if(is_neg) res = -res;

	return res;
}

char isDigits(char* str) {
	// check whether this string is digits or not 
	int length = strlen(str);

	for(int i=0;i<length;i++) {
		if(i == 0) {
			if(!(isDigit(str[i]) || str[i] == '-')) {
				return 0;
			}
			continue;
		}
		if(!(isDigit(str[i]))) {
			return 0;
		}
	}
	return 1;
}

entry* createKeyNode(char* operator, int value_num) {
	entry* res = (entry*)malloc(sizeof(entry));

	memset(res, 0, sizeof(entry));
	strcpy(res->key, operator);
	res->next = res;
	res->prev = res;
	res->length = value_num;
	if(value_num != 0) {
		res->values = (element*)malloc(value_num * sizeof(element));
	}

	res->forward_max = MAX_FORWARD;
	res->backward_max = MAX_BACKWARD;
	res->forward = (entry**)malloc(MAX_FORWARD * sizeof(entry*));
	res->backward = (entry**)malloc(MAX_BACKWARD * sizeof(entry*));

	return res;
}

// TODO : forward
entry* copyEntries(entry* head_old) {
	entry* head_new = createKeyNode("HEAD NODE", 0);

	entry* ptr_new = head_new;
	entry* ptr_old = head_old->next;

	while(ptr_old != head_old) {
		entry* temp = (entry*)malloc(sizeof(entry));
		*temp = *ptr_old;

		temp->values = (element*)malloc(temp->length * (sizeof(element)));
		for(int i=0;i<temp->length;i++) {
			(temp->values)[i].type = (ptr_old->values)[i].type;
			(temp->values)[i].entry = (ptr_old->values)[i].entry;
		}

		temp->forward = (entry**)malloc(temp->forward_max * (sizeof(entry*)));
		for(int i=0;i<temp->forward_size;i++) {
			(temp->forward)[i] = (ptr_old->forward)[i];
		}

		temp->backward = (entry**)malloc(temp->backward_max * (sizeof(entry*)));
		for(int i=0;i<temp->backward_size;i++) {
			(temp->backward)[i] = (ptr_old->backward)[i];
		}

		ptr_new->next = temp;
		temp->prev = ptr_new;
		ptr_new = temp;

		ptr_old = ptr_old->next;
	}

	ptr_new->next = head_new;
	head_new->prev = ptr_new;

	// re-assign forward and backward

	entry* visit = head_new->next;

	while(visit != head_new) {
		for(int i=0;i<visit->length;i++) {
			if((visit->values)[i].type == ENTRY) {
				(visit->values)[i].entry = findEntry(head_new, (visit->values)[i].entry->key);
			}
		}
		for(int i=0;i<visit->forward_size;i++) {
			(visit->forward)[i] = findEntry(head_new, (visit->forward)[i]->key);
		}
		for(int i=0;i<visit->backward_size;i++) {
			(visit->backward)[i] = findEntry(head_new, (visit->backward)[i]->key);
		}
		visit = visit->next;
	}

	return head_new;

}

snapshot* createSnapshot(int id) {
	snapshot* res = (snapshot*)malloc(sizeof(snapshot));

	memset(res, 0, sizeof(snapshot));
	res->next = res;
	res->prev = res;
	res->id = id;
	res->entries = copyEntries(current);

	return res;
}

int insertToEntryHead(char* operator, entry* head, int value_index) {
	// insert a member to an entry

	if(isDigits(operator)) {
		element* ele = (head->values) + value_index;
		ele->type = INTEGER;
		ele->value = getDigitsFromStr(operator);
		// return 1 means this is a number
		return 1;

	}else {
		// TODO:
		element* ele = (head->values) + value_index;
		ele->type = ENTRY;
		entry* find = findEntry(current, operator);
		if(find == NULL || (strcmp(operator, head->key) == 0)) {
			if(find == NULL)
				printf("no such key\n");
			else
				printf("not permitted\n");
			return -1;
		}
		ele->entry = find;
		addForwardToEntry(head, find);
		addBackwardToEntry(find, head);

		// return 0 means this is not a number
		return 0;
	}

}

void insertToCurrent(entry* head) {
	// insert a entry to databse 

	head->prev = current;
	head->next = current->next;
	current->next->prev = head;
	current->next = head;
	
	
}

void insertToSnapshots(snapshot* head) {
	// insert a snapshot to databse 

	head->prev = snapshots;
	head->next = snapshots->next;
	snapshots->next->prev = head;
	snapshots->next = head;
	
	
}

void entry_add(char* line, char* op) {
	int length = strlen(line);
	char operator[MAX_LINE] = {'\0'};
	int idx = 0;

	int fisrt_flag = 1;

	struct entry* head = NULL;

	int value_num = -1;
	int value_index = 0;
	int is_simple = 1;

	// get (key -> values)'s values' num
	for(int i=(strlen(op) + 1); i<length; i++) {
		if(line[i] == ' ' || line[i] == '\n') {
			value_num ++;
		}
	}

	for(int i=(strlen(op) + 1); i<length; i++) {
		if(line[i] == ' ' || line[i] == '\n') {
			// get a whole operator
			// process it
			operator[idx] = '\0';
			// printf("%s: digit: %d %d\n", operator, isDigits(operator), getDigitsFromStr(operator));
			if(fisrt_flag) {
				fisrt_flag = 0;
				// create a key node
				head = createKeyNode(operator, value_num);
			} else {
				int status = insertToEntryHead(operator, head, value_index);
				if(status == 0) {
					is_simple = 0;
				} else if(status == -1) {
					return;
				}
				value_index++;
			}

			// reset
			memset(operator, 0, MAX_LINE);
			idx = 0;
		}else {
			operator[idx] = line[i];
			idx++;
		}
	}
	head->is_simple = is_simple;

	// 1. find whether this entry exists
	entry* find = findEntry(current, head->key);
	if(find != NULL) {
		// TODO: process general entry
		if(find->is_simple && head->is_simple) {
			// copy head to find
			if(find->length != 0)
				free(find->values);
			find->length = head->length;
			find->values = (element*)malloc(find->length * sizeof(element));
			for(int i=0;i<find->length;i++) {
				(find->values)[i].type = (head->values)[i].type;
				(find->values)[i].entry = (head->values)[i].entry;
			}
			freeEntry(head);
		}else {
			// delete head's forward's backwards
			for(int i=0;i<head->forward_size;i++) {
				delBackwardEntry((head->forward)[i], head);
			}

			// copy head to find
			if(find->length != 0)
				free(find->values);
			find->length = head->length;
			find->values = (element*)malloc(find->length * sizeof(element));
			for(int i=0;i<find->length;i++) {
				(find->values)[i].type = (head->values)[i].type;
				(find->values)[i].entry = (head->values)[i].entry;
			}
			// copy forward
			for(int i=0;i<find->forward_size;i++) {
				delBackwardEntry((find->forward)[i], find);
			}
			if(find->forward_size != 0)
				free(find->forward);
			find->forward_size = head->forward_size;
			find->forward = (entry**)malloc(find->forward_max * sizeof(entry*));
			for(int i=0;i<head->forward_size;i++) {
				(find->forward)[i] = (head->forward)[i];
			}
			for(int i=0;i<find->forward_size;i++) {
				addBackwardToEntry((find->forward)[i], find);
			}
			freeEntry(head);
			updateSimple(find);
		}

		printf("ok\n");
		return;
	}
	
	// 2. insert the entry to current
	insertToCurrent(head);

	printf("ok\n");
}

void command_bye() {
	// free current
	deleteAll(current);
	if(current->length != 0)
		free(current->values);
	if(current->forward_size != 0)
		free(current->forward);
	if(current->backward_size != 0)
		free(current->backward);
	free(current);
	current = NULL;
	// free snapshots
	deleteAllSnapshots(snapshots);
	free(snapshots);
	snapshots = NULL;

	printf("bye\n");
	exit(0);
}

void command_help() {
	printf("%s", HELP);
}

void printValues(entry* target) {
	if(target == NULL) {
		printf("no such key\n");
	}else {
		printf("[");
		for(int i=0;i<target->length;i++) {
			if(i == 0) {
				if((target->values)[i].type == INTEGER) {
					printf("%d", (target->values)[i].value);
				} else {
					printf("%s", (target->values)[i].entry->key);
				}
			}
			else {
				if((target->values)[i].type == INTEGER) {
					printf(" %d", (target->values)[i].value);
				} else {
					printf(" %s", (target->values)[i].entry->key);
				}
			}
		}
		printf("]\n");
	}
}

void list_entries() {
	entry* ptr = current->next;
	int cnt = 0;

	while(ptr != current) {
		printf("%s ", ptr->key);
		printValues(ptr);
		ptr = ptr->next;
		cnt++;
	}

	if(cnt == 0) {
		printf("no entries\n");
	}
}
void list_keys() {
	entry* ptr = current->next;
	int cnt = 0;

	while(ptr != current) {
		printf("%s\n", ptr->key);
		ptr = ptr->next;
		cnt++;
	}

	if(cnt == 0) {
		printf("no keys\n");
	}
}

void list_snapshots() {
	snapshot* ptr = snapshots->next;
	int cnt = 0;

	while(ptr != snapshots) {
		printf("%d\n", ptr->id);
		ptr = ptr->next;
		cnt++;
	}

	if(cnt == 0) {
		printf("no snapshots\n");
	}
}

void command_list(char* line, char* op) {
	char op2[MAX_LINE] = {'\0'};
	int idx = 0;

	for(int i=(strlen(op) + 1); i<strlen(line); i++) {
		if(line[i] == '\n') {
			op2[idx] = '\0';
		}else {
			op2[idx] = line[i];
			idx++;
		}
	}

	if(strcmp(upcase(op2), "KEYS") == 0) {
		list_keys();

	}else if(strcmp(upcase(op2), "ENTRIES") == 0) {
		list_entries();

	}else if(strcmp(upcase(op2), "SNAPSHOTS") == 0) {
		list_snapshots();

	}else {

	}

}

void command_get(char* line, char* op) {
	char key[MAX_LINE] = {'\0'};
	int idx = 0;

	for(int i=(strlen(op) + 1); i<strlen(line); i++) {
		if(line[i] == '\n') {
			key[idx] = '\0';
		}else {
			key[idx] = line[i];
			idx++;
		}
	}

	entry* res = findEntry(current, key);

	printValues(res);

}

void command_delete(char* line, char* op) {
	char op2[MAX_LINE] = {'\0'};
	int idx = 0;

	for(int i=(strlen(op) + 1); i<strlen(line); i++) {
		if(line[i] == '\n') {
			op2[idx] = '\0';
		}else {
			op2[idx] = line[i];
			idx++;
		}
	}

	entry* res = findEntry(current, op2);
	if(res == NULL) {
		printf("no such key\n");
		return;
	}
	if(canBeDelete(res)) {
		for(int i=0;i<res->forward_size;i++) {
			delBackwardEntry((res->forward)[i], res);
			updateSimple((res->forward)[i]);
		}
		deleteEntry(current, res->key);
	}else {
		printf("not permitted\n");
		return;
	}
	printf("ok\n");
}
void command_type(char* line, char* op) {
	char op2[MAX_LINE] = {'\0'};
	int idx = 0;

	for(int i=(strlen(op) + 1); i<strlen(line); i++) {
		if(line[i] == '\n') {
			op2[idx] = '\0';
		}else {
			op2[idx] = line[i];
			idx++;
		}
	}
	entry* res = findEntry(current, op2);
	if(res == NULL) {
		printf("no such key\n");
		return;
	}
	if(res->is_simple) {
		printf("simple\n");
	}else {
		printf("general\n");
	}
}

int min(entry* res) {
	int min_val = MAX_INT;
	int temp;

	for(int i=0;i<res->length;i++) {
		if((res->values)[i].type == INTEGER) {
			temp = (res->values)[i].value;
			if(temp < min_val)
				min_val = temp;
		}else {
			temp = min((res->values)[i].entry);
			if(temp < min_val)
				min_val = temp;
		}
	}
	return min_val;
}

void command_min(char* line, char* op) {
	char op2[MAX_LINE] = {'\0'};
	int idx = 0;

	for(int i=(strlen(op) + 1); i<strlen(line); i++) {
		if(line[i] == '\n') {
			op2[idx] = '\0';
		}else {
			op2[idx] = line[i];
			idx++;
		}
	}
	entry* res = findEntry(current, op2);
	if(res == NULL) {
		printf("no such key\n");
		return;
	}
	int min_val = min(res);

	if(min_val != MAX_INT) {
		printf("%d\n", min_val);
	}
}

int max(entry* res) {
	int max_val = MIN_INT;
	int temp;

	for(int i=0;i<res->length;i++) {
		if((res->values)[i].type == INTEGER) {
			temp = (res->values)[i].value;
			if(temp > max_val)
				max_val = temp;
		}else {
			temp = max((res->values)[i].entry);
			if(temp > max_val)
				max_val = temp;
		}
	}
	return max_val;
}

void command_max(char* line, char* op) {
	char op2[MAX_LINE] = {'\0'};
	int idx = 0;

	for(int i=(strlen(op) + 1); i<strlen(line); i++) {
		if(line[i] == '\n') {
			op2[idx] = '\0';
		}else {
			op2[idx] = line[i];
			idx++;
		}
	}
	entry* res = findEntry(current, op2);
	if(res == NULL) {
		printf("no such key\n");
		return;
	}
	int max_val = max(res);

	if(max_val != MIN_INT) {
		printf("%d\n", max_val);
	}
}

int sum(entry* res) {
	int sum_val = 0;

	for(int i=0;i<res->length;i++) {
		if((res->values)[i].type == INTEGER) {
			sum_val += (res->values)[i].value;
		} else {
			sum_val += sum((res->values)[i].entry);
		}
	}

	return sum_val;
}

void command_sum(char* line, char* op) {
	char op2[MAX_LINE] = {'\0'};
	int idx = 0;

	for(int i=(strlen(op) + 1); i<strlen(line); i++) {
		if(line[i] == '\n') {
			op2[idx] = '\0';
		}else {
			op2[idx] = line[i];
			idx++;
		}
	}
	entry* res = findEntry(current, op2);
	if(res == NULL) {
		printf("no such key\n");
		return;
	}
	int sum_val = sum(res);

	printf("%d\n", sum_val);
}

int len(entry* res) {
	int len_val = 0;

	for(int i=0;i<res->length;i++) {
		if((res->values)[i].type == INTEGER) {
			len_val += 1;
		} else {
			len_val += len((res->values)[i].entry);
		}
	}

	return len_val;
}

void command_len(char* line, char* op) {
	char op2[MAX_LINE] = {'\0'};
	int idx = 0;

	for(int i=(strlen(op) + 1); i<strlen(line); i++) {
		if(line[i] == '\n') {
			op2[idx] = '\0';
		}else {
			op2[idx] = line[i];
			idx++;
		}
	}
	entry* res = findEntry(current, op2);
	if(res == NULL) {
		printf("no such key\n");
		return;
	}
	printf("%d\n", (int)(len(res)));
}

void command_rev(char* line, char* op) {
	char op2[MAX_LINE] = {'\0'};
	int idx = 0;

	for(int i=(strlen(op) + 1); i<strlen(line); i++) {
		if(line[i] == '\n') {
			op2[idx] = '\0';
		}else {
			op2[idx] = line[i];
			idx++;
		}
	}
	entry* res = findEntry(current, op2);
	if(res == NULL) {
		printf("no such key\n");
		return;
	}
	// reverse res 
	int begin = 0;
	int end = res->length - 1;
	while( begin < end ) {
		// exchange begin and end 

		int temp = (res->values)[begin].value;
		(res->values)[begin].value = (res->values)[end].value;
		(res->values)[end].value = temp;

		begin++;
		end--;
	}
	printf("ok\n");
}

void command_uniq(char* line, char* op) {
	char op2[MAX_LINE] = {'\0'};
	int idx = 0;

	for(int i=(strlen(op) + 1); i<strlen(line); i++) {
		if(line[i] == '\n') {
			op2[idx] = '\0';
		}else {
			op2[idx] = line[i];
			idx++;
		}
	}
	entry* res = findEntry(current, op2);
	if(res == NULL) {
		printf("no such key\n");
		return;
	}
	if(res->length == 0) return;

	element* new = (element*)malloc(res->length * (sizeof(element)));
	idx = 0;
	int dummy = (res->values)[0].value;
	new[idx].type = INTEGER;
	new[idx].value = dummy;
	idx++;
	
	for(int i=1;i<res->length;i++) {
		if((res->values)[i].value != dummy) {
			new[idx].type = INTEGER;
			new[idx].value = (res->values)[i].value;
			dummy = (res->values)[i].value;
			idx++;
		}else {
		}
	}
	free(res->values);
	res->values = new;
	res->length = idx;
	printf("ok\n");
	
}

void command_sort(char* line, char* op) {
	char op2[MAX_LINE] = {'\0'};
	int idx = 0;

	for(int i=(strlen(op) + 1); i<strlen(line); i++) {
		if(line[i] == '\n') {
			op2[idx] = '\0';
		}else {
			op2[idx] = line[i];
			idx++;
		}
	}
	entry* res = findEntry(current, op2);
	if(res == NULL) {
		printf("no such key\n");
		return;
	}
	
	int n = res->length;
	for(int i=0;i<n;i++) {
		int min = MAX_INT;
		int loc = -1;
		for(int j=i;j<n;j++) {
			if((res->values)[j].value < min) {
				min = (res->values)[j].value;
				loc = j;
			}
		}
		if(min != MAX_INT) {
			// exchange
			int temp = (res->values)[loc].value;
			(res->values)[loc].value = (res->values)[i].value;
			(res->values)[i].value = temp;
		}
	}
	printf("ok\n");
}

void command_rollback(char* line, char* op) {
	char op2[MAX_LINE] = {'\0'};
	int idx = 0;

	for(int i=(strlen(op) + 1); i<strlen(line); i++) {
		if(line[i] == '\n') {
			op2[idx] = '\0';
		}else {
			op2[idx] = line[i];
			idx++;
		}
	}
	int id = getDigitsFromStr(op2);

	snapshot* ptr = snapshots->next;

	snapshot* res = findSnapshot(snapshots, id);
	if(res == NULL) {
		printf("no such snapshot\n");
		return;
	}
	
	while(ptr != snapshots) {
		snapshot* next = ptr->next;
		if(ptr->id > id) {
			deleteSnapshot(snapshots, ptr->id);
		}
		ptr = next;
	}

	deleteAll(current);
	if(current->length != 0)
		free(current->values);
	if(current->forward_size != 0)
		free(current->forward);
	if(current->backward_size != 0)
		free(current->backward);
	free(current);
	entry* new = copyEntries(res->entries);
	current = new;
	printf("ok\n");
}

void command_checkout(char* line, char* op) {
	char op2[MAX_LINE] = {'\0'};
	int idx = 0;

	for(int i=(strlen(op) + 1); i<strlen(line); i++) {
		if(line[i] == '\n') {
			op2[idx] = '\0';
		}else {
			op2[idx] = line[i];
			idx++;
		}
	}
	int id = getDigitsFromStr(op2);
	snapshot* res = findSnapshot(snapshots, id);

	if(res == NULL) {
		printf("no such snapshot\n");
		return;
	}

	deleteAll(current);
	if(current->length != 0)
		free(current->values);
	if(current->forward_size != 0)
		free(current->forward);
	if(current->backward_size != 0)
		free(current->backward);
	free(current);
	entry* new = copyEntries(res->entries);
	current = new;
	printf("ok\n");
}

void command_snapshot(char* line, char* op) {
	snapshot* res = createSnapshot(snapshot_id);
	insertToSnapshots(res);
	printf("saved as snapshot %d\n", snapshot_id);
	snapshot_id++;
}

void command_drop(char* line, char* op) {
	char op2[MAX_LINE] = {'\0'};
	int idx = 0;

	for(int i=(strlen(op) + 1); i<strlen(line); i++) {
		if(line[i] == '\n') {
			op2[idx] = '\0';
		}else {
			op2[idx] = line[i];
			idx++;
		}
	}
	int id = getDigitsFromStr(op2);
	snapshot* res = findSnapshot(snapshots, id);

	if(res == NULL) {
		printf("no such snapshot\n");
		return;
	}

	deleteSnapshot(snapshots, id);

	printf("ok\n");
}

// NOTE : start from here
void command_purge(char* line, char* op) {
	char key[MAX_LINE] = {'\0'};
	int idx = 0;

	for(int i=(strlen(op) + 1); i<strlen(line); i++) {
		if(line[i] == '\n') {
			key[idx] = '\0';
		}else {
			key[idx] = line[i];
			idx++;
		}
	}

	int canDelete = 1;
	// first check whether we can delete this entry in all states
	entry* res = findEntry(current, key);
	if(res != NULL) {
		if(!canBeDelete(res)) {
			canDelete = 0;
		}
	}
	// delete the entry from all snapshots
	snapshot* ptr = snapshots->next;
	
	while(ptr != snapshots) {
		res = findEntry(ptr->entries, key);
		
		if(res != NULL) {
			if(!canBeDelete(res)) {
				canDelete = 0;
			}
		}
		ptr = ptr->next;
	}

	if(canDelete == 0) {
		printf("not permitted\n");
		return;
	}
	// do the real delete operation below

	// delete the entry from current
	res = findEntry(current, key);
	if(res != NULL) {
		if(canBeDelete(res)) {
			for(int i=0;i<res->forward_size;i++) {
				delBackwardEntry((res->forward)[i], res);
				// updateSimple((res->forward)[i]);
			}
			deleteEntry(current, key);
		}
	}
	// delete the entry from all snapshots
	ptr = snapshots->next;
	
	while(ptr != snapshots) {
		res = findEntry(ptr->entries, key);
		
		if(res != NULL) {
			if(canBeDelete(res)) {
				for(int i=0;i<res->forward_size;i++) {
					delBackwardEntry((res->forward)[i], res);
					// updateSimple((res->forward)[i]);
				}
				deleteEntry(ptr->entries, key);
			}
		}
		ptr = ptr->next;
	}
	printf("ok\n");
}

void command_push(char* line, char* op) {
	int length = strlen(line);
	char operator[MAX_LINE] = {'\0'};
	int idx = 0;

	int fisrt_flag = 1;

	int value_num = -1;
	int value_index = 0;

	entry* target = NULL;
	entry* find = NULL;

	element* new_values = NULL;
	int new_length = 0;

	entry* find_nodes[MAX_FORWARD] = {NULL};
	int find_idx = 0;

	// get (key -> values)'s values' num
	for(int i=(strlen(op) + 1); i<length; i++) {
		if(line[i] == ' ' || line[i] == '\n') {
			value_num ++;
		}
	}

	for(int i=(strlen(op) + 1); i<length; i++) {
		if(line[i] == ' ' || line[i] == '\n') {
			// get a whole operator
			// process it
			operator[idx] = '\0';
			// printf("%s: digit: %d %d\n", operator, isDigits(operator), getDigitsFromStr(operator));
			if(fisrt_flag) {
				fisrt_flag = 0;
				// key 
				target = findEntry(current, operator);
				if(target == NULL) {
					printf("no such key\n");
					return;
				}
			} else {
				// push values
				if(value_index == 0) {
					new_length = value_num + target->length;
					new_values = (element*)malloc(new_length * (sizeof(element)));
					if(isDigits(operator)) {
						new_values[value_num - 1].type = INTEGER;
						new_values[value_num - 1].value = getDigitsFromStr(operator);
					}else {
						// TODO : more careful
						find = findEntry(current, operator);
						find_nodes[find_idx++] = find;
						if(find == NULL || (strcmp(operator, target->key) == 0)) {
							printf("not permitted\n");
							return;
						}
						new_values[value_num - 1].type = ENTRY;
						new_values[value_num - 1].entry = find;
					}

					for(int i=0;i<target->length;i++) {
						new_values[value_num + i].type = (target->values)[i].type;
						new_values[value_num + i].entry = (target->values)[i].entry;
					}

					if(value_index == (value_num - 1)) {
						// commit change
						free(target->values);
						target->values = new_values;
						target->length = new_length;
						for(int i=0;i<find_idx;i++) {
							addForwardToEntry(target, find_nodes[i]);
							addBackwardToEntry(find_nodes[i], target);
						}
						if(find_idx != 0) {
							target->is_simple = 0;
						} 
					}

					value_index++;
				}else {
					if(isDigits(operator)) {
						new_values[value_num - 1 - value_index].type = INTEGER;
						new_values[value_num - 1 - value_index].value = getDigitsFromStr(operator);
					}else {
						find = findEntry(current, operator);
						find_nodes[find_idx++] = find;
						if(find == NULL || (strcmp(operator, target->key) == 0)) {
							// TODO : rollback
							printf("not permitted\n");
							return;
						}
						new_values[value_num - 1 - value_index].type = ENTRY;
						new_values[value_num - 1 - value_index].entry = find;
					}
					if(value_index == (value_num - 1)) {
						// commit change
						free(target->values);
						target->values = new_values;
						target->length = new_length;
						for(int i=0;i<find_idx;i++) {
							addForwardToEntry(target, find_nodes[i]);
							addBackwardToEntry(find_nodes[i], target);
						}
						if(find_idx != 0) {
							target->is_simple = 0;
						} 
					}
					value_index++;
				}
			}

			// reset
			memset(operator, 0, MAX_LINE);
			idx = 0;
		}else {
			operator[idx] = line[i];
			idx++;
		}
	}

	printf("ok\n");
	
}

void command_pop(char* line, char* op) {
	char op2[MAX_LINE] = {'\0'};
	int idx = 0;

	for(int i=(strlen(op) + 1); i<strlen(line); i++) {
		if(line[i] == '\n') {
			op2[idx] = '\0';
		}else {
			op2[idx] = line[i];
			idx++;
		}
	}
	entry* res = findEntry(current, op2);

	if(res == NULL) {
		printf("no such key\n");
		return;
	}

	// pop the front value
	if(res->length == 0) {
		printf("nil\n");
		return;
	}

	int new_length = res->length - 1;
	element* new_values = (element*)malloc(new_length * (sizeof(element)));

	for(int i=0;i<new_length;i++) {
		new_values[i].type = (res->values)[i + 1].type;
		new_values[i].entry = (res->values)[i + 1].entry;
	}

	if((res->values)[0].type == INTEGER) {
		printf("%d\n", (res->values)[0].value);
	}else {
		printf("%s\n", (res->values)[0].entry->key);
	}

	// delete forward
	if((res->values)[0].type == ENTRY) {
		entry* find = findEntry(current, (res->values)[0].entry->key);
		delForwardEntry(res, find);
		delBackwardEntry(find, res);
	}

	free(res->values);
	res->values = new_values;
	res->length = new_length;
	updateSimple(res);

}

void command_append(char* line, char* op) {
	int length = strlen(line);
	char operator[MAX_LINE] = {'\0'};
	int idx = 0;

	int fisrt_flag = 1;

	int value_num = -1;
	int value_index = 0;

	entry* target = NULL;
	entry* find = NULL;

	element* new_values = NULL;
	int new_length = 0;

	entry* find_nodes[MAX_FORWARD] = {NULL};
	int find_idx = 0;

	// get (key -> values)'s values' num
	for(int i=(strlen(op) + 1); i<length; i++) {
		if(line[i] == ' ' || line[i] == '\n') {
			value_num ++;
		}
	}

	for(int i=(strlen(op) + 1); i<length; i++) {
		if(line[i] == ' ' || line[i] == '\n') {
			// get a whole operator
			// process it
			operator[idx] = '\0';
			// printf("%s: digit: %d %d\n", operator, isDigits(operator), getDigitsFromStr(operator));
			if(fisrt_flag) {
				fisrt_flag = 0;
				// key 
				target = findEntry(current, operator);
				if(target == NULL) {
					printf("no such key\n");
					return;
				}
			} else {
				// append values
				if(value_index == 0) {
					new_length = value_num + target->length;
					new_values = (element*)malloc(new_length * (sizeof(element)));
					if(isDigits(operator)) {
						new_values[target->length].type = INTEGER;
						new_values[target->length].value = getDigitsFromStr(operator);
					}else {
						// TODO : more careful
						find = findEntry(current, operator);
						find_nodes[find_idx++] = find;
						if(find == NULL || (strcmp(operator, target->key) == 0)) {
							printf("not permitted\n");
							return;
						}
						new_values[target->length].type = ENTRY;
						new_values[target->length].entry = find;
					}

					for(int i=0;i<target->length;i++) {
						new_values[i].type = (target->values)[i].type;
						new_values[i].entry = (target->values)[i].entry;
					}

					if(value_index == (value_num - 1)) {
						// commit change
						free(target->values);
						target->values = new_values;
						target->length = new_length;
						for(int i=0;i<find_idx;i++) {
							addForwardToEntry(target, find_nodes[i]);
							addBackwardToEntry(find_nodes[i], target);
						}
						if(find_idx != 0) {
							target->is_simple = 0;
						} 
					}

					value_index = target->length + 1;
				}else {
					if(isDigits(operator)) {
						new_values[value_index].type = INTEGER;
						new_values[value_index].value = getDigitsFromStr(operator);
					}else {
						find = findEntry(current, operator);
						find_nodes[find_idx++] = find;
						if(find == NULL || (strcmp(operator, target->key) == 0)) {
							// TODO : rollback
							printf("not permitted\n");
							return;
						}
						new_values[value_index].type = ENTRY;
						new_values[value_index].entry = find;
					}
					if(value_index == (value_num - 1 + target->length)) {
						// commit change
						free(target->values);
						target->values = new_values;
						target->length = new_length;
						for(int i=0;i<find_idx;i++) {
							addForwardToEntry(target, find_nodes[i]);
							addBackwardToEntry(find_nodes[i], target);
						}
						if(find_idx != 0) {
							target->is_simple = 0;
						} 
					}
					value_index++;
				}
			}

			// reset
			memset(operator, 0, MAX_LINE);
			idx = 0;
		}else {
			operator[idx] = line[i];
			idx++;
		}
	}

	printf("ok\n");
	
}

void command_pick(char* line, char* op) {
	int length = strlen(line);
	char operator[MAX_LINE] = {'\0'};
	int idx = 0;

	int fisrt_flag = 1;

	int value_index = 0;

	entry* target = NULL;

	for(int i=(strlen(op) + 1); i<length; i++) {
		if(line[i] == ' ' || line[i] == '\n') {
			// get a whole operator
			// process it
			operator[idx] = '\0';
			// printf("%s: digit: %d %d\n", operator, isDigits(operator), getDigitsFromStr(operator));
			if(fisrt_flag) {
				fisrt_flag = 0;
				// key 
				target = findEntry(current, operator);
				if(target == NULL) {
					printf("no such key\n");
					return;
				}
			} else {
				// pick values
				if(value_index == 0) {
					int index = getDigitsFromStr(operator) - 1;

					if(index < target->length && index >= 0) {
						if((target->values)[index].type == INTEGER) {
							printf("%d\n", (target->values)[index].value);
						}else {
							printf("%s\n", (target->values)[index].entry->key);
						}
					}else {
						printf("index out of range\n");
						return;
					}
					value_index++;
				}else {
					
				}
			}
			// reset
			memset(operator, 0, MAX_LINE);
			idx = 0;
		}else {
			operator[idx] = line[i];
			idx++;
		}
	}
}

void command_pluck(char* line, char* op) {
	int length = strlen(line);
	char operator[MAX_LINE] = {'\0'};
	int idx = 0;

	int fisrt_flag = 1;

	int value_index = 0;

	entry* target = NULL;

	for(int i=(strlen(op) + 1); i<length; i++) {
		if(line[i] == ' ' || line[i] == '\n') {
			// get a whole operator
			// process it
			operator[idx] = '\0';
			// printf("%s: digit: %d %d\n", operator, isDigits(operator), getDigitsFromStr(operator));
			if(fisrt_flag) {
				fisrt_flag = 0;
				// key 
				target = findEntry(current, operator);
				if(target == NULL) {
					printf("no such key\n");
					return;
				}
			} else {
				// pluck values
				if(value_index == 0) {
					int index = getDigitsFromStr(operator) - 1;

					if(index < target->length && index >= 0) {
						if((target->values)[index].type == INTEGER) {
							printf("%d\n", (target->values)[index].value);
						}else {
							printf("%s\n", (target->values)[index].entry->key);
						}
						// delete it
						int new_length = target->length - 1;
						element* new_values = (element*)malloc(new_length * (sizeof(element)));
						int copy_idx = 0;

						for(int i=0;i<target->length;i++) {
							if(i != index) {
								new_values[copy_idx].type = (target->values)[i].type;
								new_values[copy_idx].entry = (target->values)[i].entry;
								copy_idx++;
							}
						}

						if((target->values)[index].type == ENTRY) {
							entry* find = findEntry(current, (target->values)[index].entry->key);
							delForwardEntry(target, find);
							delBackwardEntry(find, target);
						}

						free(target->values);
						target->values = new_values;
						target->length = new_length;

						updateSimple(target);

					}else {
						printf("index out of range\n");
						return;
					}
					value_index++;
				}else {
					
				}
			}
			// reset
			memset(operator, 0, MAX_LINE);
			idx = 0;
		}else {
			operator[idx] = line[i];
			idx++;
		}
	}
}

void forward(entry* target, char** keys, int* idx) {
	for(int i=0;i<target->forward_size;i++) {
		keys[*idx] = (char*)malloc(MAX_KEY);
		strcpy(keys[*idx], (target->forward)[i]->key);
		*idx = *idx + 1;
		forward((target->forward)[i], keys, idx);
	}
}

void backward(entry* target, char** keys, int* idx) {
	for(int i=0;i<target->backward_size;i++) {
		keys[*idx] = (char*)malloc(MAX_KEY);
		strcpy(keys[*idx], (target->backward)[i]->key);
		*idx = *idx + 1;
		backward((target->backward)[i], keys, idx);
	}
}

void stringSort(char** arr,int size) {
	for(int i=0;i<size;i++) {
		char* min = arr[i];
		int loc = i;
		for(int j=i + 1;j<size;j++) {
			if(strcmp(arr[j], min) < 0) {
				min = arr[j];
				loc = j;
			}
		}
		if(loc != i) {
			char* temp = arr[loc];
			arr[loc] = arr[i];
			arr[i] = temp;
		}
	}
}

void command_forward(char* line, char* op) {
	char op2[MAX_LINE] = {'\0'};
	int idx = 0;

	for(int i=(strlen(op) + 1); i<strlen(line); i++) {
		if(line[i] == '\n') {
			op2[idx] = '\0';
		}else {
			op2[idx] = line[i];
			idx++;
		}
	}
	entry* res = findEntry(current, op2);

	if(res == NULL) {
		printf("no such entry\n");
		return;
	}
	char* keys[MAX_FORWARD];
	int size = 0;
	int same_index = 0;

	forward(res, keys, &size);

	stringSort(keys, size);
	for(int i=0;i<size;i++) {
		// do not print same keys
		if(i != 0 && (strcmp(keys[same_index], keys[i]) == 0)) {
			continue;
		} else {
			same_index = i;
		}
		if(i == 0) {
			printf("%s", keys[i]);
		}else {
			printf(", %s", keys[i]);
		}
	}
	if(size == 0) {
		printf("nil");
	}
	printf("\n");

}

void command_backward(char* line, char* op) {
	char op2[MAX_LINE] = {'\0'};
	int idx = 0;

	for(int i=(strlen(op) + 1); i<strlen(line); i++) {
		if(line[i] == '\n') {
			op2[idx] = '\0';
		}else {
			op2[idx] = line[i];
			idx++;
		}
	}
	entry* res = findEntry(current, op2);

	if(res == NULL) {
		printf("no such entry\n");
		return;
	}

	char* keys[MAX_FORWARD] = {NULL};
	int size = 0;
	int same_index = 0;

	backward(res, keys, &size);

	stringSort(keys, size);
	for(int i=0;i<size;i++) {
		// do not print same keys
		if(i != 0 && (strcmp(keys[same_index], keys[i]) == 0)) {
			continue;
		} else {
			same_index = i;
		}
		if(i == 0) {
			printf("%s", keys[i]);
		}else {
			printf(", %s", keys[i]);
		}
	}
	if(size == 0) {
		printf("nil");
	}
	printf("\n");
}

void parseCommand(char* line, char* op) {
	// printf("op :%s\n",op);
	if(strcmp(upcase(op), "HELP") == 0) {
		command_help();
	} else if(strcmp(upcase(op), "BYE") == 0) {
		command_bye();
	} else if(strcmp(upcase(op), "SET") == 0) {
		entry_add(line, op);
	} else if(strcmp(upcase(op), "GET") == 0) {
		command_get(line, op);
	} else if(strcmp(upcase(op), "LIST") == 0) {
		command_list(line, op);
	} else if(strcmp(upcase(op), "DEL") == 0) {
		command_delete(line, op);
	} else if(strcmp(upcase(op), "TYPE") == 0) {
		command_type(line, op);
	} else if(strcmp(upcase(op), "MIN") == 0) {
		command_min(line, op);
	} else if(strcmp(upcase(op), "MAX") == 0) {
		command_max(line, op);
	} else if(strcmp(upcase(op), "SUM") == 0) {
		command_sum(line, op);
	} else if(strcmp(upcase(op), "LEN") == 0) {
		command_len(line, op);
	} else if(strcmp(upcase(op), "REV") == 0) {
		command_rev(line, op);
	} else if(strcmp(upcase(op), "UNIQ") == 0) {
		command_uniq(line, op);
	} else if(strcmp(upcase(op), "SORT") == 0) {
		command_sort(line, op);
	} else if(strcmp(upcase(op), "ROLLBACK") == 0) {
		command_rollback(line, op);
	} else if(strcmp(upcase(op), "CHECKOUT") == 0) {
		command_checkout(line, op);
	} else if(strcmp(upcase(op), "SNAPSHOT") == 0) {
		command_snapshot(line, op);
	} else if(strcmp(upcase(op), "DROP") == 0) {
		command_drop(line, op);
	} else if(strcmp(upcase(op), "PURGE") == 0) {
		command_purge(line, op);
	} else if(strcmp(upcase(op), "POP") == 0) {
		command_pop(line, op);
	} else if(strcmp(upcase(op), "PUSH") == 0) {
		command_push(line, op);
	} else if(strcmp(upcase(op), "APPEND") == 0) {
		command_append(line, op);
	} else if(strcmp(upcase(op), "PICK") == 0) {
		command_pick(line, op);
	} else if(strcmp(upcase(op), "PLUCK") == 0) {
		command_pluck(line, op);
	} else if(strcmp(upcase(op), "FORWARD") == 0) {
		command_forward(line, op);
	} else if(strcmp(upcase(op), "BACKWARD") == 0) {
		command_backward(line, op);
	}
	
}

void systemInit() {
	// create a head node
	current = createKeyNode("HEAD_NODE", 0);
	int Snapshothead = -1;
	snapshots = createSnapshot(Snapshothead);
}

int main(void) {

	char line[MAX_LINE];
	char op[MAX_LINE];

	systemInit();

	while (true) {
		#ifndef AUTOTEST
		printf("> ");
		#endif

		if (NULL == fgets(line, MAX_LINE, stdin)) {
			printf("\n");
			command_bye();
			return 0;
		}

		//
		// TODO
		//

		int length = strlen(line);
		memset(op, 0, MAX_LINE);
		for(int i=0;i<length;i++) {
			if(i == (length - 1)) {
				op[i] = '\0';
				break;
			}
			if(line[i] != ' ') {
				op[i] = line[i];
			} else {
				op[i] = '\0';
				break;
			}
		}

		parseCommand(line, op);
		printf("\n");
  	}

	return 0;
}
